% Find incidence matrix of a graph
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% function toIncidence = toIncidence(DG,varargin);
%  
%   This function will convert from an adjacency matrix of DG to the
%   associated incidence matrix for DG
%
%   INPUTS:     DG - directed graph's adjacency matrix
%               
%   OUTPUTS:    incidenceMatrix - directed graph's incidence matrix            
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function incidenceMatrix = toIncidence(DG,varargin)

% Some variable declarations
[xmax ymax]=size(DG);
incidenceMatrix = zeros(xmax,size(size(DG)));
edgeList = zeros(2,size(size(DG))); % 1 is to, 2 is from
n = 1;

% We go through, find every edge and number them as was specified in the
% problem specification
for y = 1:xmax
    for x = 1:ymax
        if (DG(x,y) == 1),
            edgeList(1,n) = x;
            edgeList(2,n) = y;
            n = n + 1;
        end;
    end;
end;

% set max n, but we added 1 too many times earlier
nmax = n - 1;

% now we traverse the edge list and fill our incidence matrix
% if this was an undirected graph we merely change the -1 to +1
for n = 1:nmax
    incidenceMatrix(edgeList(1,n),n) = 1;
    incidenceMatrix(edgeList(2,n),n) = - 1;
end;

